// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package search

import (
	"cmd/go/internal/base"
	"cmd/go/internal/cfg"
	"cmd/go/internal/fsys"
	"fmt"
	"go/build"
	"io/fs"
	"os"
	"path"
	"path/filepath"
	"regexp"
	"strings"
)

// 匹配表示匹配单个包模式的结果。
type Match struct {
	pattern string   // 模式本身
	Dirs    []string // 如果模式是本地的，则可能包含匹配包的目录
	Pkgs    []string // 匹配包（导入路径）
	Errs    []error  // 将模式与包匹配时出错，而不是加载那些包时出错

	// 即使len（Pkgs）>0，Errs也可能为非空，这表示某些匹配
	// 可以找到包，但结果可能不完整。
	// 如果len（Pkgs）==0&&len（Errs）==0，则模式是格式良好的，但没有
	// 匹配任何包。
}

// NewMatch返回描述给定模式的匹配，
// 不解析其包或错误。
func NewMatch(pattern string) *Match {
	return &Match{pattern: pattern}
}

// Pattern返回要匹配的模式。
func (m *Match) Pattern() string { return m.pattern }

// AddError将MatchError包装错误附加到m.Errs。
func (m *Match) AddError(err error) {
	m.Errs = append(m.Errs, &MatchError{Match: m, Err: err})
}

// Literal报告模式是否没有通配符和元模式。
// None
// 文字模式最多必须匹配一个包。
func (m *Match) IsLiteral() bool {
	return !strings.Contains(m.pattern, "...") && !m.IsMeta()
}

// 本地报告模式是否必须从特定根或
// 目录，例如文件系统路径或单个模块。
func (m *Match) IsLocal() bool {
	return build.IsLocalImport(m.pattern) || filepath.IsAbs(m.pattern)
}

// Meta报告模式是否是表示
// 多个包，如“std”、“cmd”或“all”。
func (m *Match) IsMeta() bool {
	return IsMetaPackage(m.pattern)
}

// IsMetaPackage检查名称是否是扩展到多个包的保留包名称。
func IsMetaPackage(name string) bool {
	return name == "std" || name == "cmd" || name == "all"
}

// MatchError表示尝试匹配时发生的错误
// 图案
type MatchError struct {
	Match *Match
	Err   error
}

func (e *MatchError) Error() string {
	if e.Match.IsLiteral() {
		return fmt.Sprintf("%s: %v", e.Match.Pattern(), e.Err)
	}
	return fmt.Sprintf("pattern %s: %v", e.Match.Pattern(), e.Err)
}

func (e *MatchError) Unwrap() error {
	return e.Err
}

// MatchPackages将m.Pkgs设置为包含所有
// 可以在匹配
// 图案模式必须为“全部”（所有包）、“标准”（标准
// 软件包），“cmd”（标准命令），或包含“…”的路径。
// None
// 如果任何错误可能导致包集不完整，
// MatchPackages将这些错误附加到m.Errs。
func (m *Match) MatchPackages() {
	m.Pkgs = []string{}
	if m.IsLocal() {
		m.AddError(fmt.Errorf("internal error: MatchPackages: %s is not a valid package pattern", m.pattern))
		return
	}

	if m.IsLiteral() {
		m.Pkgs = []string{m.pattern}
		return
	}

	match := func(string) bool { return true }
	treeCanMatch := func(string) bool { return true }
	if !m.IsMeta() {
		match = MatchPattern(m.pattern)
		treeCanMatch = TreeCanMatchPattern(m.pattern)
	}

	have := map[string]bool{
		"builtin": true, // 忽略仅为文档而存在的伪包
	}
	if !cfg.BuildContext.CgoEnabled {
		have["runtime/cgo"] = true // 步行时忽略
	}

	for _, src := range cfg.BuildContext.SrcDirs() {
		if (m.pattern == "std" || m.pattern == "cmd") && src != cfg.GOROOTsrc {
			continue
		}
		src = filepath.Clean(src) + string(filepath.Separator)
		root := src
		if m.pattern == "cmd" {
			root += "cmd" + string(filepath.Separator)
		}
		err := fsys.Walk(root, func(path string, fi fs.FileInfo, err error) error {
			if err != nil {
				return err // 可能是权限错误，可能会干扰匹配。
			}
			if path == src {
				return nil // GOROOT/src和GOPATH/src不能包含包。
			}

			want := true
			// 避免.foo、\u foo和testdata目录树。
			_, elem := filepath.Split(path)
			if strings.HasPrefix(elem, ".") || strings.HasPrefix(elem, "_") || elem == "testdata" {
				want = false
			}

			name := filepath.ToSlash(path[len(src):])
			if m.pattern == "std" && (!IsStandardImportPath(name) || name == "cmd") {
				// 名称“std”只是标准库。
				// 如果名称为cmd，则它是命令树的根。
				want = false
			}
			if !treeCanMatch(name) {
				want = false
			}

			if !fi.IsDir() {
				if fi.Mode()&fs.ModeSymlink != 0 && want && strings.Contains(m.pattern, "...") {
					if target, err := fsys.Stat(path); err == nil && target.IsDir() {
						fmt.Fprintf(os.Stderr, "warning: ignoring symlink %s\n", path)
					}
				}
				return nil
			}
			if !want {
				return filepath.SkipDir
			}

			if have[name] {
				return nil
			}
			have[name] = true
			if !match(name) {
				return nil
			}
			pkg, err := cfg.BuildContext.ImportDir(path, 0)
			if err != nil {
				if _, noGo := err.(*build.NoGoError); noGo {
					// 该包实际上不存在，因此记录两个包
					// 也不是错误。
					return nil
				}
				// 导入路径时出错，但路径不匹配，
				// 这就是Match承诺要做的。
				// 忽略导入错误。
			}

			// 如果我们正在扩展“cmd”，请跳过main
			// cmd/供应商下的包。至少在
			// 2017年3月，这里有一个
			// 出售工具。
			if m.pattern == "cmd" && pkg != nil && strings.HasPrefix(pkg.ImportPath, "cmd/vendor") && pkg.Name == "main" {
				return nil
			}

			m.Pkgs = append(m.Pkgs, name)
			return nil
		})
		if err != nil {
			m.AddError(err)
		}
	}
}

var modRoot string

func SetModRoot(dir string) {
	modRoot = dir
}

// MatchDirs将m.Dirs设置为包含所有
// 可能与本地模式匹配。模式必须以绝对值开头
// 路径，或“/”或“./”。在Windows上，图案可以使用斜杠或反斜杠
// 分离器或两者的混合。
// None
// 如果任何错误可能导致目录集不完整，
// MatchDirs将这些错误附加到m.Errs。
func (m *Match) MatchDirs() {
	m.Dirs = []string{}
	if !m.IsLocal() {
		m.AddError(fmt.Errorf("internal error: MatchDirs: %s is not a valid filesystem pattern", m.pattern))
		return
	}

	if m.IsLiteral() {
		m.Dirs = []string{m.pattern}
		return
	}

	// 清除路径并创建匹配谓词。
	// filepath.Clean删除“/”前缀（和Windows上的“\”。我们需要
	// 保留这些，因为它们在匹配模式和
	// 返回导入路径。
	cleanPattern := filepath.Clean(m.pattern)
	isLocal := strings.HasPrefix(m.pattern, "./") || (os.PathSeparator == '\\' && strings.HasPrefix(m.pattern, `.\`))
	prefix := ""
	if cleanPattern != "." && isLocal {
		prefix = "./"
		cleanPattern = "." + string(os.PathSeparator) + cleanPattern
	}
	slashPattern := filepath.ToSlash(cleanPattern)
	match := MatchPattern(slashPattern)

	// 查找目录以开始扫描。
	// 可能更聪明，但这一次
	// 现在已经足够了，因为。。。通常在
	// 路的尽头。
	i := strings.Index(cleanPattern, "...")
	dir, _ := filepath.Split(cleanPattern[:i])

	// 模式以./或../开头。
	// path.Clean将丢弃./而不是../。
	// 我们需要保留模式匹配的./
	// 和在返回的导入路径中。

	if modRoot != "" {
		abs, err := filepath.Abs(dir)
		if err != nil {
			m.AddError(err)
			return
		}
		if !hasFilepathPrefix(abs, modRoot) {
			m.AddError(fmt.Errorf("directory %s is outside module root (%s)", abs, modRoot))
			return
		}
	}

	err := fsys.Walk(dir, func(path string, fi fs.FileInfo, err error) error {
		if err != nil {
			return err // 可能是权限错误，可能会干扰匹配。
		}
		if !fi.IsDir() {
			return nil
		}
		top := false
		if path == dir {
			// Walk从dir开始并递归。对于递归情况，
			// 路径是filepath.Join的结果，它调用filepath.Clean。
			// 不过，最初的案例没有清理，所以我们明确地这样做。
			// None
			// 这会将类似“/io/”的路径转换为“io”。如果没有这一步，运行
			// “cd$GOROOT/src；go list./io/…”会错误地跳过io
			// 包，因为将前缀“/”前置到不干净的路径会
			// 结果为“//io”，匹配（“.//io”）返回false。
			top = true
			path = filepath.Clean(path)
		}

		// 避免.foo、_foo和testdata目录树，但不要避免“.”或“.”。
		_, elem := filepath.Split(path)
		dot := strings.HasPrefix(elem, ".") && elem != "." && elem != ".."
		if dot || strings.HasPrefix(elem, "_") || elem == "testdata" {
			return filepath.SkipDir
		}

		if !top && cfg.ModulesEnabled {
			// 忽略子目录中的其他模块。
			if fi, err := fsys.Stat(filepath.Join(path, "go.mod")); err == nil && !fi.IsDir() {
				return filepath.SkipDir
			}
		}

		name := prefix + filepath.ToSlash(path)
		if !match(name) {
			return nil
		}

		// 如果我们能导入目录，或者如果我们不能导入目录，我们就保留它
		// 由于Go源文件无效。这意味着包含
		// 将生成（并失败）分析错误，而不是静默跳过
		// 与模式不匹配。跳过了Go 1.5和更早版本，但是
		// 行为意味着人们错过了严重的错误。
		// 见golang.org/issue/11407。
		if p, err := cfg.BuildContext.ImportDir(path, 0); err != nil && (p == nil || len(p.InvalidGoFiles) == 0) {
			if _, noGo := err.(*build.NoGoError); noGo {
				// 该包实际上不存在，因此记录两个包
				// 也不是错误。
				return nil
			}
			// 导入路径时出错，但路径不匹配，
			// 这就是Match承诺要做的。
			// 忽略导入错误。
		}
		m.Dirs = append(m.Dirs, name)
		return nil
	})
	if err != nil {
		m.AddError(err)
	}
}

// TreeCanMachPattern（模式）（名称）报告是否
// 名称或名称的子项可能与模式匹配。
// 模式与matchPattern接受的有限全局相同。
func TreeCanMatchPattern(pattern string) func(name string) bool {
	wildCard := false
	if i := strings.Index(pattern, "..."); i >= 0 {
		wildCard = true
		pattern = pattern[:i]
	}
	return func(name string) bool {
		return len(name) <= len(pattern) && hasPathPrefix(pattern, name) ||
			wildCard && strings.HasPrefix(name, pattern)
	}
}

// MatchPattern（模式）（名称）报告是否
// 名称与模式匹配。模式是一个有限的全局
// 其中“…”表示“任意字符串”的模式
// 没有其他特殊语法。
// 不幸的是，有两种特殊情况。引用“go帮助包”：
// None
// 首先，/。。。在模式的末尾可以匹配一个空字符串，
// 因此，网络/。。。匹配net及其子目录中的包，如net/http。
// 第二，任何包含通配符的斜杠分隔模式元素
// 参与供应商路径中“供应商”元素的匹配
// 包装，以便。/。。。与的子目录中的包不匹配
// /vendor或/mycode/vendor，但是/vendor/。。。和./mycode/vendor/。。。做
// 但是，请注意，名为vendor的目录本身包含代码
// 不是供应商程序包：cmd/vendor将是名为vendor的命令，
// 还有模式cmd/。。。与之匹配。
func MatchPattern(pattern string) func(name string) bool {
	// 将模式转换为正则表达式。
	// 跟踪的策略/。。。是否将其嵌套在显式的？表示
	// 供应商排除的策略是更改不匹配的
	// 供应商字符串到不允许的代码点（vendorChar）并使用
	// “（除该代码点外的任何内容）*”作为。。。通配符。
	// 这有点复杂但显然是另一种选择，
	// 也就是像大多数shell glob matchers一样的手写搜索，
	// 这太容易了。
	// 使用包regexp可以保证线性时间匹配。

	const vendorChar = "\x00"

	if strings.Contains(pattern, vendorChar) {
		return func(name string) bool { return false }
	}

	re := regexp.QuoteMeta(pattern)
	re = replaceVendor(re, vendorChar)
	switch {
	case strings.HasSuffix(re, `/`+vendorChar+`/\.\.\.`):
		re = strings.TrimSuffix(re, `/`+vendorChar+`/\.\.\.`) + `(/vendor|/` + vendorChar + `/\.\.\.)`
	case re == vendorChar+`/\.\.\.`:
		re = `(/vendor|/` + vendorChar + `/\.\.\.)`
	case strings.HasSuffix(re, `/\.\.\.`):
		re = strings.TrimSuffix(re, `/\.\.\.`) + `(/\.\.\.)?`
	}
	re = strings.ReplaceAll(re, `\.\.\.`, `[^`+vendorChar+`]*`)

	reg := regexp.MustCompile(`^` + re + `$`)

	return func(name string) bool {
		if strings.Contains(name, vendorChar) {
			return false
		}
		return reg.MatchString(replaceVendor(name, vendorChar))
	}
}

// replaceVendor返回替换的结果
// x中带有repl的非尾随供应商路径元素。
func replaceVendor(x, repl string) string {
	if !strings.Contains(x, "vendor") {
		return x
	}
	elem := strings.Split(x, "/")
	for i := 0; i < len(elem)-1; i++ {
		if elem[i] == "vendor" {
			elem[i] = repl
		}
	}
	return strings.Join(elem, "/")
}

// 警告不匹配警告与任何包不匹配的模式。
func WarnUnmatched(matches []*Match) {
	for _, m := range matches {
		if len(m.Pkgs) == 0 && len(m.Errs) == 0 {
			fmt.Fprintf(os.Stderr, "go: warning: %q matched no packages\n", m.pattern)
		}
	}
}

// ImportPath返回用于给定命令行的匹配路径。
// 它调用ImportPathsQuiet，然后调用WarnUnmatched。
func ImportPaths(patterns []string) []*Match {
	matches := ImportPathsQuiet(patterns)
	WarnUnmatched(matches)
	return matches
}

// ImportPathsQuiet与ImportPaths类似，但不会警告没有匹配的模式。
func ImportPathsQuiet(patterns []string) []*Match {
	var out []*Match
	for _, a := range CleanPatterns(patterns) {
		m := NewMatch(a)
		if m.IsLocal() {
			m.MatchDirs()

			// 如果包已被删除，请将文件导入路径更改为常规导入路径
			// 在GOPATH或GOROOT中。我们这里不报告错误；装载导入
			// （或类似情况）将稍后报告。
			m.Pkgs = make([]string, len(m.Dirs))
			for i, dir := range m.Dirs {
				absDir := dir
				if !filepath.IsAbs(dir) {
					absDir = filepath.Join(base.Cwd(), dir)
				}
				if bp, _ := cfg.BuildContext.ImportDir(absDir, build.FindOnly); bp.ImportPath != "" && bp.ImportPath != "." {
					m.Pkgs[i] = bp.ImportPath
				} else {
					m.Pkgs[i] = dir
				}
			}
		} else {
			m.MatchPackages()
		}

		out = append(out, m)
	}
	return out
}

// CleanPatterns返回用于给定命令行的模式。信息技术
// 规范化模式，但不计算任何匹配项。图案
// 如果不是本地或绝对路径，它会在“@”之后保留文本以避免
// 修改版本查询。
func CleanPatterns(patterns []string) []string {
	if len(patterns) == 0 {
		return []string{"."}
	}
	var out []string
	for _, a := range patterns {
		var p, v string
		if build.IsLocalImport(a) || filepath.IsAbs(a) {
			p = a
		} else if i := strings.IndexByte(a, '@'); i < 0 {
			p = a
		} else {
			p = a[:i]
			v = a[i:]
		}

		// 参数可以是文件路径或导入路径。
		// 作为对Windows开发人员的礼貌，请重写\to/
		// 在看起来像导入路径的参数中。
		// 不要替换绝对路径中的斜杠。
		if filepath.IsAbs(p) {
			p = filepath.Clean(p)
		} else {
			if filepath.Separator == '\\' {
				p = strings.ReplaceAll(p, `\`, `/`)
			}

			// 以规范形式放置参数，但保留前导。/。
			if strings.HasPrefix(p, "./") {
				p = "./" + path.Clean(p)
				if p == "./." {
					p = "."
				}
			} else {
				p = path.Clean(p)
			}
		}

		out = append(out, p+v)
	}
	return out
}

// hasPathPrefix报告路径s是否以
// 前缀中的元素。
func hasPathPrefix(s, prefix string) bool {
	switch {
	default:
		return false
	case len(s) == len(prefix):
		return s == prefix
	case len(s) > len(prefix):
		if prefix != "" && prefix[len(prefix)-1] == '/' {
			return strings.HasPrefix(s, prefix)
		}
		return s[len(prefix)] == '/' && s[:len(prefix)] == prefix
	}
}

// hasFilepathPrefix报告路径s是否以
// 前缀中的元素。
func hasFilepathPrefix(s, prefix string) bool {
	switch {
	default:
		return false
	case len(s) == len(prefix):
		return s == prefix
	case len(s) > len(prefix):
		if prefix != "" && prefix[len(prefix)-1] == filepath.Separator {
			return strings.HasPrefix(s, prefix)
		}
		return s[len(prefix)] == filepath.Separator && s[:len(prefix)] == prefix
	}
}

// IsStandardImportPath报告是否应考虑$GOROOT/src/path
// 标准分发的一部分。出于历史原因，我们允许人们添加
// 他们自己的代码使用$GOROOT而不是$GOPATH，但我们假设
// 代码将以域名（第一个元素中的点）开头。
// None
// 请注意，此函数用于评估是否在GOROOT中找到目录
// 应被视为标准库的一部分。不应该用它来决定
// 应拒绝在GOPATH中找到的目录：GOPATH中的目录
// 在第一个元素中不需要点，他们只是抓住机会
// 标准库中的未来冲突。
func IsStandardImportPath(path string) bool {
	i := strings.Index(path, "/")
	if i < 0 {
		i = len(path)
	}
	elem := path[:i]
	return !strings.Contains(elem, ".")
}

// IsRelativePath报告是否应将模式解释为目录
// 相对于当前目录的路径，而不是模式匹配
// 导入路径。
func IsRelativePath(pattern string) bool {
	return strings.HasPrefix(pattern, "./") || strings.HasPrefix(pattern, "../") || pattern == "." || pattern == ".."
}

// InDir检查路径是否位于以dir为根的文件树中。
// 如果是这样，InDir将返回相对于dir的等效路径。
// 如果不是，InDir将返回一个空字符串。
// 即使存在符号链接，InDir也会做出一些努力来取得成功。
func InDir(path, dir string) string {
	if rel := inDirLex(path, dir); rel != "" {
		return rel
	}
	xpath, err := filepath.EvalSymlinks(path)
	if err != nil || xpath == path {
		xpath = ""
	} else {
		if rel := inDirLex(xpath, dir); rel != "" {
			return rel
		}
	}

	xdir, err := filepath.EvalSymlinks(dir)
	if err == nil && xdir != dir {
		if rel := inDirLex(path, xdir); rel != "" {
			return rel
		}
		if xpath != "" {
			if rel := inDirLex(xpath, xdir); rel != "" {
				return rel
			}
		}
	}
	return ""
}

// inDirLex与inDir类似，但只检查文件名的词法形式。
// 它不考虑符号链接。
// TODO（rsc）：这是str.HasFilePathPrefix的副本，修改为
// 返回后缀。str.HasFilePathPrefix的大多数用法应该
// 我打电话给InDir。
func inDirLex(path, dir string) string {
	pv := strings.ToUpper(filepath.VolumeName(path))
	dv := strings.ToUpper(filepath.VolumeName(dir))
	path = path[len(pv):]
	dir = dir[len(dv):]
	switch {
	default:
		return ""
	case pv != dv:
		return ""
	case len(path) == len(dir):
		if path == dir {
			return "."
		}
		return ""
	case dir == "":
		return path
	case len(path) > len(dir):
		if dir[len(dir)-1] == filepath.Separator {
			if path[:len(dir)] == dir {
				return path[len(dir):]
			}
			return ""
		}
		if path[len(dir)] == filepath.Separator && path[:len(dir)] == dir {
			if len(path) == len(dir)+1 {
				return "."
			}
			return path[len(dir)+1:]
		}
		return ""
	}
}
